# -*- coding:utf-8 -*-
import heapq
class Solution:
    # 1
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if len(tinput)<=0 or k<=0 or len(tinput)<k:
            return []
        if len(tinput)==k:
            return sorted(tinput)
        a = []
        for i in range(len(tinput)):
            if len(a)<k:
                a.append(tinput[i])
            else:
                a = heapq.nlargest(k,a)
                if tinput[i] >= a[0]:
                    continue
                else:
                    a[0]=  tinput[i]
        return a[::-1]


    # 2
    def find_least_k_nums(self,alist, k):
        l = len(alist)
        if not alist or l==0 or k<=0 or k>l:
            return []
        start = 0
        end =l-1
        self.paretion(alist,start,end)
        return alist[:k]

    def paretion(self,alist,start,end):
        if end<=start:
            return
        base = alist[start]
        i1 ,i2 = start,end
        while start<end:
            while start<end and alist[end]>=base:
                end-=1
            alist[start] = alist[end]
            while start<end and alist[start]<=base:
                start+=1
            alist[end] = alist[start]
        alist[start] = base
        self.paretion(alist,i1,start-1)
        self.paretion(alist,start+1,i2)
        return start
#     3
    def find_least_k_nums2(self,alist, k):
        length = len(alist)
        #if length == k:
        #    return alist
        if not alist or k <=0 or k > length:
            return
        start = 0
        end = length - 1
        index = self.paretion(alist, start, end)
        while index != k:
            if index > k:
                index = self.paretion(alist, start, index - 1)
            elif index < k:
                index = self.paretion(alist, index + 1, end)
        return alist[:k]





tinput = [4,5,1,6,2,7,3,8]
s = Solution()
# print(s.GetLeastNumbers_Solution(tinput, 4))
# print(s.find_least_k_nums(tinput, 4))
print(s.find_least_k_nums(tinput, 5))